/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

/**
 * 
 * {
    val: 1,
    next: {
        val: 2,
        next: {
            val: 3,
            next: {
                val: 4,
                next: null
            }
        }
 * }
 */
function reverseList(head: ListNode | null): ListNode | null {

    const result = new ListNode(0, null)
    function fn(node: ListNode | null): ListNode {
        if (!node) return result
        if (node.next) {
            const temp = fn(node.next)
            temp.next = new ListNode(node.val, null)
            return temp.next
        } else {
            result.val = node.val
        }
        return result

    }
    return fn(head)
};

// 迭代
function reverseList1(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current: ListNode | null = head;

    while (current !== null) {
        const nextTemp: ListNode | null = current.next; // 保存下一个节点 {val:2,next:{...}} {val:3,next:{...}}
        current.next = prev; // 反转指针 {val:1,next:null} {val:2,next:{val:1,next:null}}
        prev = current; // 前移prev {val:1,next:null}
        current = nextTemp; // 前移current {val:2,next:{...}}
    }

    return prev; // prev最终成为新的头节点
}

// 递归
function reverseListRecursive(head: ListNode | null): ListNode | null {
    // 递归终止条件：空链表或只有一个节点
    if (head === null || head.next === null) {
        return head;
    }

    // 递归反转剩余部分
    const newHead = reverseListRecursive(head.next);

    // 将当前节点的下一个节点的next指向当前节点（反转指针）
    head.next.next = head;
    // 将当前节点的next置为null（防止循环）
    head.next = null;

    return newHead; // 返回新的头节点
}